Short for “discrete cosine transform,” a DCT is a technique for representing waveform data as a weighted sum of cosines, and is commonly used for image compression. Closely related to the discrete Fourier transform (“DFT”), discrete cosine transformations involve manipulation of real numbers only, offering energy compaction improvements over DFT by eliminating artificial discontinuities that appear in DFT.
Attributed to these and other appealing qualities, the DCT is popularly deployed in a broad class of coding techniques, known as transform coding or block quantization, which attempt to reduce image signal redundancy by representing signals with a new set of orthogonal bases, reducing the spatial correlations that occur between adjacent pixels. Using direct cosine transformations, a fraction of the transform coefficients is encoded, with tolerable deterioration in image fidelity.
JPEG (pronounced “jay-peg”) is one standardized DCT-based image compression mechanism for still images. An acronym for “Joint Photographic Experts Group” (the original name of the committee that wrote the standard), JPEG is designed to compress either full-color or gray-scale images of natural, real-world scenes. Conventional JPEG typically works well on photographs, naturalistic artwork, and similar material, but is not as effective on lettering, simple cartoons, or line drawings. In addition to conventional JPEG, other DCT-based image compression mechanisms are well known in the data compression art.
FIG. 1 is a block diagram illustrating the baseline algorithm or encoding process utilized by the conventional JPEG coding standard. The processes and functionalities associated with each step of the conventional JPEG image compression algorithm, including the image data input step (Step S102), the image partitioning step (Step S104), the forward DCT step (Step S105), the quantization step (Step S106), the zigzag re-sequencing step (Step S107), the entropy encoding step (Step S109), and the compressed data output step (Step S110) are well known in the art, and for this reason these steps are largely not described herein, for the sake of brevity.
FIGS. 2A to 2C illustrate one problem associated with the conventional JPEG image compression mechanism. FIG. 2A depicts an example of an 8×8 vector of normalized quantized coefficients that would typically be output by the quantization step (Step S106), for an 8×8 random image patch. As depicted in FIG. 2B, the zigzag re-ordering step (Step S107) attempts to group low-frequency coefficients at the top of a vector, mapping the 8×8 vector to a 1×64 vector, by zigzagging through the coefficients as shown. The resulting 1×64 vector, illustrated in FIG. 2C, is used in the entropy encoding process (Step S109) to further compress the quantized image data.
While attempting to group coefficients of like magnitude, the trellis-coding approach used by conventional JPEG, which zigzags back and fourth between quantized DCT coefficients, does not necessarily preserve coefficient adjacency, and the zigzag path often introduces jump discontinuities. For these and other reasons, zigzag re-sequencing of quantized DCT coefficients according to the conventional JPEG image compression mechanism typically results in an increased loss of coefficient magnitudes, decreasing overall compression efficiency.
It is therefore considered highly desirable to provide an enhanced DCT-based image compression mechanism which increases compression efficiency. In particular, it is desirable to provide an image compression mechanism which orders DCT coefficients in a manner which reduces jump discontinuities, and preserves coefficient adjacency, resulting in more efficient JPEG block coding.